<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <!-- 最小高度树 -->
    <script>
      var findMinHeightTrees = function (n, edges) {
        // 求最小高度，其实是对这个无向图进行 层序遍历，从叶子节点开始遍历，直到所有节点遍历完毕
        // g是每个节点的相邻节点信息，deg是每个节点所在边的数量
        let g = Array(n)
            .fill()
            .map(() => []),
          deg = Array(n).fill(0)
        // 遍历所有的边，也就是遍历两两相邻的节点
        for (let [x, y] of edges) {
          // 两个节点xy相邻是相互的，x的邻居中有y，y的邻居中也有x
          g[x].push(y)
          g[y].push(x)
          // 更新两个节点所在边的数量
          deg[x]++, deg[y]++
        }
        let q = [],
          res = []
        // 首先取出第一层节点
        for (let i = 0; i < n; i++) {
          if (deg[i] == 1) q.push(i)
        }
        // 借助队列，广度优先的进行遍历
        while (q.length) {
          let size = q.length
          let level = []
          // 遍历当前层的所有节点
          for (let i = 0; i < size; i++) {
            let cur = q.shift()
            // 遍历过的节点，要沿着边的方向继续向深遍历
            for (let next of g[cur]) {
              // 由于当前节点已经弹出，逻辑上，cur节点已经从树中删除掉了
              // 那么，就需要更新和cur节点在一条边的节点的度的数量
              deg[next]--
              // 剪掉叶子节点cur之后，next节点如果成为叶子节点，那么他就是下一层的节点了
              if (deg[next] == 1) {
                // 将下一层的节点放到队列和level数组中
                q.push(next)
                level.push(next)
              }
            }
          }
          if (level.length) res.push(level)
        }
        return res[res.length - 1]
      }
      console.log(
        findMinHeightTrees(6, [
          [3, 0],
          [3, 1],
          [3, 2],
          [3, 4],
          [5, 4]
        ])
      )
    </script>
  </body>
</html>
